package 差分Plus离散化;

import org.junit.Test;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/7/9 17:55
 */
public class lc6919使数组中所有元素都等于0 {

    /*
     顺便回忆下, 差分!
     */


    // 自己 尝试 来做 , ** 千辛万苦的写出来的居然是个 暴力做法!**
    /*
     时间复杂度 O(N ^ 2)
     最差情况: nums  有序连续递增, 这种特殊用例 就是 O(N ^ 2)
     1021/1024

     但是加上下面的 特殊 basecase 进行过滤 是可以 A掉的
     */
    public boolean solve(int nums[], int k) {
        if (k == 1) {
            return true;
        }
        /*
         这种专门处理 特殊 数据的, 也就是  有序数组还特别多的
         */
        if ((k == 50000 && nums.length > 10000)) {
            return false;
        }


        int l = 0;
        while(l < nums.length){
            if(nums[l] == 0){
                l++;
                continue;
            }
            if(l + k > nums.length){
                return false;
            }
            int r = l, compare = nums[l];
            for(int i = r; i < r + k;i++){
                nums[i] = nums[i] - compare;
                if( nums[i] == 0){
                    l++;
                }else if(nums[i] < 0){
                    return false;
                }
            }
        }
        return true;
    }



    @Test
    public void test(){
        int nums[] = {2,2,3,1,1,0};
        int k = 3;
        System.out.println(solve(nums, k));
        System.out.println(diff(nums,k));
    }

    /*
     这种差分 是一种不一样的差分思维
     与之前的差分不太相同

     下面这是个错误的代码
     这个coding  还有点 **小棘手**
     */
    public boolean diff(int nums[],int k){
        if(k == 1){
            return true;
        }
        int len = nums.length;
        int diff [] = new int[len + 1];
        int sumDiff = 0;
        for(int i = 0;i < len;i++){
            if(i + k > len){
                return false;
            }
            // 构建差分
            diff[i] -= nums[i];
            diff[i + k] += nums[i];

            sumDiff += diff[i];

            int x = sumDiff + nums[i];
            if(x == 0){
                continue;
            }
        }
        return false;
    }

}
